// 递归搜索与回溯 - 决策树问题
// 当一个题目可以使用决策树画出来，那么也可以通过递归的方法解决
// 画决策树，要保证不重不漏，实际上就是暴搜
// 使用全局变量进行统计，避免递归函数头传参问题
// 设计递归函数头，是否需要记录本次决策的位置，层数，个数等信息
// 回溯时注意本层计算完成后，直接在本层回溯，返回上一个位置
// 经典题目：全排列，子集

// 例题 15：
// 在二维网格 grid 上，有 4 种类型的方格：
//
//        1 表示起始方格。且只有一个起始方格。
//        2 表示结束方格，且只有一个结束方格。
//        0 表示我们可以走过的空方格。
//        -1 表示我们无法跨越的障碍。
//        返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目。
//
//        每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格。
//
//
//
//        示例 1：
//
//        输入：[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
//        输出：2
//        解释：我们有以下两条路径：
//        1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
//        2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)
//        示例 2：
//
//        输入：[[1,0,0,0],[0,0,0,0],[0,0,0,2]]
//        输出：4
//        解释：我们有以下四条路径：
//        1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
//        2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
//        3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
//        4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)
//        示例 3：
//
//        输入：[[0,1],[2,0]]
//        输出：0
//        解释：
//        没有一条路能完全穿过每一个空的方格一次。
//        请注意，起始和结束方格可以位于网格中的任意位置。
//
//
//        提示：
//
//        1 <= grid.length * grid[0].length <= 20


// 解题思路：
// 找到数组中有多少个 0，记为 总步数
// 从起点上下左右搜索，如果不是障碍就递归，步数++
// 如果遇到 2，检查步数，是否等于总步数，等于 ret++, 然后返回
// 如果不等于总步数，返回

public class UniquePathsIII {
    int m;
    int n;
    boolean[][] check;
    int ret;
    int count;
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};

    public int uniquePathsIII(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        check = new boolean[m][n];

        int bx = 0;
        int by = 0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == 0){
                    count++;
                }else if(grid[i][j] == 1){
                    bx = i;
                    by = j;
                }
            }
        }
        count++;
        check[bx][by] = true;
        dfs(grid, bx, by, 0);

        return ret;
    }

    public void dfs(int[][] grid, int i, int j, int step){
        if(grid[i][j] == 2){
            if(step == count){
                ret++;
            }
            return;
        }

        for(int k = 0; k < 4; k++){
            int x = i + dx[k];
            int y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && check[x][y] == false && grid[x][y] != -1){
                check[x][y] = true;
                dfs(grid, x, y, step + 1);
                check[x][y] = false;
            }
        }
    }
}
